Field of the Invention
The present invention relates in general to the field of information processing, and more specifically to a system and method for consolidating data from various product data models.
Description of the Related Art
A configurable product can be described by a configuration model having a set of configuration rules. A configurable product can be conceptually broken down into sets of selectable families and features of families that make up each product. A family represents a classification of a particular type of feature. Families are typically classified as groups of features with the same functional purpose. Example families for an automobile are “engines,” “tires,” “seats,” and “exterior paint color.” Families can also represent other groups such as market areas. For example, a family can include a marketing region such as USA, Canada, Mexico, Europe, or any other region. Families can be represented in terms of the minimum and maximum number of features that must be present in a configuration from a family for the configuration to be valid. A common family minimum and maximum or “(min, max)” is (1, 1). This notation means that exactly one feature from the family must be part of a configuration for the configuration to be valid. Other common (min, max) settings are (0, 1), meaning that either no features or a single feature from the family must be present in a configuration for it to be valid, and (0, −1), meaning that zero or any positive number of features from the family must be present in a configuration for it to be valid.
A feature represents an option that can be ordered on a product. All features are members of a family. Features are both assigned optionalities and used to qualify other features and the optionalities assigned to them. An example feature from the engine family is a “4.8 liter V8.” Features relate to each other via ordering codes or optionalities. Example optionalities include “S”, “O”, “M”, and “N,” which translate to standard, optional, mandatory, and not available. A specific example would be “the 4.8 liter V8 engine is standard on the GS trim.”
Features relate to each other via configuration rules. A rule can be characterized as generally including a ‘left hand side’, (LHS), a ‘right hand side’ (RHS), and a specified relationship between the LHS and RHS. Each LHS feature may be associated with one or more RHS features, which indicates that a single feature in the LHS may be constrained or otherwise qualified by one or more RHS features. The RHS describes when a rule is in effect and what features are particularly affected. For example, a rule with a RHS of “XA, XB” means that the rule is in effect in cases where you have at least XA and XB in a buildable configuration, and XA and XB are features particularly affected by the rule along with the LHS feature. Configuration rules include optionalities that define a relationship between the LHS and RHS. Further exemplary discussion of LHS and RHS rule concepts is described in Gupta et al., U.S. Pat. No. 5,825,651 entitled “Method and Apparatus for Maintaining and Configuring Systems.”
A configuration rule includes a main feature, an optionality, one or more constraints, and an applicable timeframe. As an example:
Main featureOptionalityConstraintsTimeframe4.8 liter V8SXL & USMay-December 2003Rule 1
Rule 1 means “the 4.8 liter V8 is standard with the XL trim and US market from May to December 2003.” The main feature represents the feature that is being affected by the rule. Optionalities can be positive or negative: positive optionalities state that the main feature can work with the constraints; negative optionalities state the main feature cannot work with the constraints. Constraints qualify the rule and can be an arbitrary Boolean expression of features such as AND, NOT, and OR operators. In the rules below, a “.” indicates an AND operation, a “˜” indicates a NOT operation, and a “+” indicates an OR operation. The timeframe specifies when the other rule elements are effective.
A buildable configuration describes what features can and can't exist with other features of a product. The example rule above defines a buildable configuration in the following way: “the 4.8 liter V8 is buildable (because it is standard) with the combination of XL and US.” If the combination of features, such as of XL and US, is not buildable, the example rule is inactive. Consequently, even though the engine is buildable with that combination, if the combination is not buildable, the three features together are not a buildable configuration. A rule that would make the example rule inactive is the following:
Main featureOptionalityConstraintsTimeframeXLNUSSeptember 2002Rule 2
Rule 2 means “the XL trim main feature is not available with US from September of 2002 onward.” Until the XL main feature is made available with the US by changing the optionality from “N” to one that expresses a positive relationship, there will not be a buildable configuration for XL, US, and the 4.8 L engine.
Thus, a rule defines a buildable configuration between its main feature and its constraints only. A rule does NOT define a buildable configuration relationship between the members of its constraints. A separate rule must define that buildable configuration. Consequently, all rules together for a product define the complete product buildable configurations. In order to determine if the three features in the example rule (the main feature and the constraints) are a buildable configuration, the rules written on each of those features (i.e. where each feature is the main feature) should to be considered jointly. Inactive rules do not define buildable configurations until they become active.
A “model” refers to a collection of rules that define the buildable configurations of one or more products.
Referring to FIG. 2, the families in each model are internally organized in accordance with a directed acyclic graph (“DAG”) 200. The DAG contains an edge between a child family and a parent family if there exists a rule with a LHS feature that belongs to the child family and a RHS feature that belongs to the parent family. The DAG organization allows a child family to reference an ancestor but not the other way around. Cyclic references within a model as in FIG. 4 can produce ambiguities within the model.
Each model contains variations of the buildable configurations of the product. For example, a company may market a product with a particular set of standard features in one region and market the same product with a different set of standard features in another region. For example, in an automotive context, a V6 engine may be standard for a particular automobile model in one country, and a V8 engine may be standard for the particular automobile model in another country. In a computer context, a power supply with a 110V input may be standard in one country and a power supply with a 220V input may be standard in another country.
Defining and maintaining the configuration space for a large product can often be difficult to do in a single configuration model. In order to limit the complexity and facilitate maintenance the configuration space is often defined in multiple configuration models. Each of these models are then assigned a set of defining constraints that specify which portion of the overall configuration space for the product it is defining. An example breakdown of the configuration space definition for an automotive vehicle could be into 3 separate models. Each model would define the configuration space of the automobile in one of 3 countries: USA, Canada, or Mexico. In this example each configuration model would have as a defining constraint one of the features representing each country. In the USA model the only allowable configurations would all contain the “USA” feature. Although not specifically included in this example, time can also be a defining constraint.
A model may contain labels that describe the time period and space over which the model applies (also referred to as “model defining constraints”). For example, a model which describes the availability of cars in the United States during the years 2004 to 2006 may have defining constraints of “CARS.USA.2004-2006” while a model that describes the availability of all vehicles in North America during 2005 may have defining constraints of “{CARS+TRUCKS}.{USA+CANADA+MEXICO}.2005”.
While it is convenient to have this logical separation of the configuration space for maintenance purposes it is often desired to provide a single unified model that represents the configuration space for the entire product. The resulting unified configuration model can then be used to answer any questions that one of the original models could answer and it will give the same result. The set of allowable feature combinations for the unified model should be equivalent to the union of allowable feature combinations for each of the original configuration models.
Thus, despite the differences in various models, it is often desirable to combine the multiple models into a consolidated model having a unified set of rules (also referred to as “stitched rules”). Referring to FIG. 5, the conventional consolidation system 500 includes a model 502 that represents a set of three models that may be created and maintained separately. Model 504 is, for example, a configuration model that describes how a particular product may be built and sold for the USA market. Model 506 is a configuration model that describes how the same product may be built and sold for the Canadian market. Model 508 is a configuration model that describes how the same product may be built and sold for the Mexican market. Models 504, 506, and 508 may be combined into a single model 512 by conventional consolidation (also referred to as “stitching”) processes 510. The consolidated model 512 will contain stitched rules that represent all the information present in the original three models. However, in many circumstances the conventional consolidations processes 510 produce unspecified configuration buildables in consolidated model 512. “Unspecified configuration buildables” are configuration buildables included in consolidated model 512 that are not defined in any of the source models, i.e. models 504, 506, and 508. An unspecified configuration buildable is, thus, an error that can have significant adverse consequences. Conventional consolidation processes do not automatically detect unspecified configuration buildables and correct them. Since models can contain thousands, hundreds of thousands, or more rules, a high degree of automation is often a key to success for modeling and model data driven technologies.
Referring to FIG. 1, for example, assume models 102 and 104 are two configuration models with the following rules:                Model 102: model defining constraints={MKT1}                    MKT1 O ALL            ENG1 S ALL                        Model 104: model defining constraints={MKT2}                    MKT2 O ALL            ENG1 S ALL            ENG2 O ALL                        
The rules in models 102 and 104 are interpreted as allowing the following buildable configurations:                Model 102:                    MKT1.ENG1                        Model 104:                    MKT2.ENG1            MKT2.ENG2                        
An example conventional consolidation process 510 that simply combined the rules from models 102 and 104 using a simple aggregation process would yield a consolidated model 106 with the following rules:                Model 106: model defining constraints (“MDC”)={MKT1+MKT2}                    MKT1 O ALL            MKT2 O ALL            ENG1 S ALL            ENG2 O ALL                        
The rules of model 106 are interpreted as allowing the following buildable configurations:                Model 106:                    MKT1.ENG1 (corresponds to element 108)            MKT1.ENG2 (corresponds to element 112)            MKT2.ENG1 (corresponds to element 110)            MKT2.ENG2 (corresponds to element 110)                        
Model 106 includes the model space defined by the model defining constraints 108 of model 102 and the model space defined by the model defining constraints of 110 of model 104. Unfortunately, in addition to representing the stitched rules of models 102 and 104, model 106 also includes an unspecified buildable configuration “MKT1.ENG2” 112. In the embodiment of FIG. 1, buildable configurations of model 104 have been extended into the model defining constraints MKT1 space 114. Model defining constraints space MKT2 space 116 accurately contains only the buildable configurations of model 104.
The consolidated model should faithfully represent the buildable configurations of the products represented by models 102 and 104 without including any errors such as the unspecified buildable configurations 112. Conventional consolidation processes attempt to solve this problem by modifying, adding, and removing stitched rules so that rules from each source model do not extend outside of the space defined by their source model's defining constraints.
An example enhanced conventional consolidation process 510 that combined the rules from models 102 and 104, constraining each to their source model's defining constraints, would yield a consolidated model 406 with the following rules:                Model 406: model defining constraints={MKT1+MKT2}                    MKT1 O ALL (source model 102's defining constraints={MKT1})            ENG1 S MKT1 (source model 102's defining constraints={MKT1})            MKT2 O ALL (source model 104's defining constraints={MKT2})            ENG1 S MKT2 (source model 104's defining constraints={MKT2})            ENG2 O MKT2 (source model 104's defining constraints={MKT2})                        
The rules of model 406 are interpreted as allowing the following buildable configurations:                Model 406:                    MKT1.ENG1            MKT2.ENG1            MKT2.ENG2                        
The new model 406 accurately combines the intent of source models 102 and 104 without introducing new unspecified buildable combinations.
Although consolidation appears to be the straight forward process of adding all the rules from each model being consolidated and qualifying each rule with the model defining constraint label that indicates the origin of the rule in a consolidated model, the actual conventional process is not that simple due to constraints on the model's representation of families. To avoid creation of ambiguous models, the consolidation process typically must also ensure that the families in the consolidated model 512 can be organized into a DAG as described above. However, the conventional consolidation process 510 violates this constraint.
Following is pseudo code for a conventional consolidation process produced using an appropriately programmed computer and model data. The “//” forward slash symbols represent the start and end of explanatory comments:
def performConventionalStitching(rules, mdc, dag):
                // Defines the method “performConventionalStitching” to consolidate one or more models using the rules in the models, the model defining constraints (mdc), and the DAG of the model.//        
stitchedRules={ }                // collects the consolidated rules for the consolidated model. //        
for each rule in rules:                // Sequentially process each rule in the models being consolidated. //        
stitchedRule=rule.intersect(mdc)                // Intersect the rule being processed with a model qualifier space, i.e. the configurations for which the model applies. Intersection Examples wherein A1, B1, and B2 represent model qualifier spaces:        (X1 S A1)∩A1=X1 S A1        (X1 S A1)∩B1=X1 S A1.B1        (X1 S B2)∩B1=Ø        (B1 S ALL)∩B1=B1 S ALL        (B2 S ALL)∩B1=Ø        (A1 S ALL)∩A1.B2=A1 S B2 //        
if(stitchedRule !=Ø):                // If the intersection is not empty . . . //        
stitchedRule=removeDAGCycles(stitchedRule, dag)                // Remove any qualifiers that produce cyclical references within the DAG. //        
stitchedRules.add(stitchedRule)                // Add stitched rules to the set of stitchedRules of the consolidated model. //        
return stitchedRules
def removeDAGCycles(rule, dag):
                // Defines the method “removeDAGCycles” to remove qualifiers of the rule that produce cyclical relationships within the DAG. //        
remove qualifiers from the rule that are ancestor families of the main feature (i.e. the LHS of the rule) in the DAG.
The following represents the example application of the conventional model consolidation process. Consider two source models using the following rules:                Model 602: model defining constraints={SER1}                    MKT1 O ALL, MKT2 O ALL            ENG1 S MKT1, ENG2 S MKT2, ENG2 O MKT1            SER1 S {ENG1+ENG2}                        Model 612: model defining constraints={SER2}                    MKT1 O ALL, MKT2 O ALL            ENG1 S MKT1, ENG2 S MKT2            SER2 S (ENG1+ENG2)                        
FIG. 6 illustrates how the rules for each family combine to yield a set of buildable configurations. In addition, FIG. 6 illustrates how conventional stitching combines the buildable combinations of models 602 and 612 to create the consolidated model 622. Shaded portions represent indicated buildable configurations. For clarity, FIG. 6 ignores the effects of the optionalities (‘S’, ‘O’, . . . ) of the rules. FIG. 3 illustrates a DAG for models 602 and 612.                Model 602: model defining constraints={SER1}                    The MKT rules restrict the model to buildable combinations 604: all buildable combinations that include MKT1 and MKT2.            The ENG rules restrict the model to buildable combinations 606: all buildable combinations that include MKT1.ENG1, MKT1.ENG2, MKT2.ENG2.            The SER rule restricts the model to buildable combinations 608: all buildable combinations that include SER2.            The intersection of the buildable combinations allowed by MKT (604), ENG (606) and SER (608) are the buildable combinations allowed by the entire model (610): all buildable combinations that include MKT1.ENG1.SER1, MKT1.ENG2.SER1, MKT2.ENG2.SER1.                        Model 612: model defining constraints={SER2}                    The MKT rules restrict the model to buildable combinations 614: all buildable combinations that include MKT1 and MKT 2.            The ENG rules restrict the model to buildable combinations 616: all buildable combinations that include MKT1.ENG1, MKT2.ENG2.            The SER rule restricts the model to buildable combinations 618: all buildable combinations that include SER2.            The intersection of the buildable combinations allowed by MKT (614), ENG (616) and SER (618) are the buildable combinations allowed by the entire model (620): all buildable combinations that include MKT1.ENG1.SER2, MKT2.ENG2.SER2.                        
Following are the consolidated model rules generated using conventional consolidation process 510 and above pseudo code:                Model 622: model defining constraints={SER1+SER2}                    MKT1 O ALL, MKT2 O ALL            MKT1 O ALL, MKT2 O ALL (624)            ENG1 S MKT1, ENG2 S MKT2, ENG2 O MKT1            ENG1 S MKT1, ENG2 S MKT2 (626)            SER1 S {ENG1+ENG2}            SER2 S {ENG1+ENG2} (628)                        
The MKT and ENG rules could not be qualified by the model defining constraints because doing so would have caused a cycle in the family relationship DAG as depicted in FIG. 4. Especially, the “ENG2 O MKT1” rule was not qualified by the model defining constraint SER1. The result is that the unspecified buildable configuration “MKT1.ENG2.SER2” 636 was added to the buildable combinations 630 of the combined model 622.